1. Field of the Invention
This invention relates to computer systems, and more particularly to a multiprocessing computer system with data storage array systems allowing for linear and orthogonal expansion of data storage capacity and bandwidth by means of a switching network.
2. Description of Related Art
A typical multiprocessing computer system generally involves one or more data storage units which are connected to a plurality of Central Processor Units (CPU's), either directly through an input/output (I/O) bus, or through an I/O control unit and one or more I/O channels. The function of the data storage units is to store data and programs which the CPU's use in performing particular data processing tasks.
One type of multiprocessing system known in the art is described in U.S. Pat. No. 4,228,496, assigned to the assignee of the present invention. A simplified version of the computer system architecture taught in that patent is shown in FIG. 1. The system shown therein provides for a high degree of reliability by providing two redundant interprocessor busses IPB interconnecting a plurality of CPU's 1. However, where cost predominates over reliability concerns, a single interprocessor bus may be used in a multiprocessing system.
The system shown in FIG. 1 includes a plurality of data storage units 2, each coupled to at least two CPU's 1 by means of an I/O bus 3 (or, alternatively, through redundant I/O control units). Various type of data storage units are used in such a data processing system. A typical system may include one or more large capacity tape units and/or disk drives (magnetic, optical, or semiconductor). Again, if cost is a predominant factor, single connections rather than dual connections can be used.
Any CPU 1 in the architecture can access any directly coupled data storage unit 2. In addition, any CPU 1 in the architecture can access any other data storage unit 2 indirectly over the IPB via another CPU 1.
The architecture shown in FIG. 1 allows for linear expansion of computing resources by adding CPU's 1 to the interprocessor bus IPB, in the "x" direction (see FIG. 1). The architecture also allows for linear expansion of I/O resources by adding data storage units 2 to the I/O busses or channels, in the orthogonal "y" direction. Expansion in the x and y directions can be independent of each other, limited only by performance and physical constraints.
Thus, the current art provides for linear expansion of CPU's and orthogonal and linear expansion of individual data storage units 2 to correspond to the storage requirements of the CPU's.
More recently, highly reliable disk array data storage systems have been introduced to the market. Such disk array systems present a challenge when coupled within such a multiprocessor architecture.
Disk array systems are of various types. A research group at the University of California, Berkeley, in a paper entitled "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Patterson, et al., Proc. ACM SIGMOD, June 1988, has catalogued a number of different types by defining five architectures under the acronym "RAID" (for Redundant Arrays of Inexpensive Disks).
A RAID 1 architecture involves providing a duplicate set of "mirror" data storage units and keeping a duplicate copy of all data on each pair of data storage units. A number of implementations of RAID 1 architectures have been made, in particular by Tandem Computers Incorporated.
A RAID 2 architecture stores each bit of each word of data, plus Error Detection and Correction (EDC) bits for each word, on separate disk drives. For example, U.S. Pat. No. 4,722,085 to Flora et al. discloses a disk drive memory using a plurality of relatively small, independently operating disk subsystems to function as a large, high capacity disk drive having an unusually high fault tolerance and a very high data transfer bandwidth. A data organizer adds 7 EDC bits (determined using the well-known Hamming code) to each 32-bit data word to provide error detection and error correction capability. The resultant 39-bit word is written, one bit per disk drive, on to 39 disk drives. If one of the 39 disk drives fails, the remaining 38 bits of each stored 39-bit word can be used to reconstruct each 32-bit data word on a word-by-word basis as each data word is read from the disk drives, thereby obtaining fault tolerance.
A RAID 3 architecture is based on the concept that each disk drive storage unit has internal means for detecting a fault or data error. Therefore, it is not necessary to store extra information to detect the location of an error; a simpler form of parity-based error correction can thus be used. In this approach, the contents of all storage units subject to failure are "Exclusive OR'd" (XOR'd) to generate parity information. The resulting parity information is stored in a single redundant storage unit. If a storage unit fails, the data on that unit can be reconstructed on to a replacement storage unit by XOR'ing the data from the remaining storage units with the parity information. Such an arrangement has the advantage over the mirrored disk RAID 1 architecture in that only one additional storage unit is required for "N" storage units. A further aspect of the RAID 3 architecture is that the disk drives are operated in a coupled manner, similar to a RAID 2 system, and a single disk drive is designated as the parity unit. One implementation of a RAID 3 architecture is the Micropolis Corporation Parallel Drive Array, Model 1804 SCSI, which uses four parallel, synchronized disk drives and one redundant parity drive. The failure of one of the four data disk drives can be remedied by the use of the parity bits stored on the parity disk drive. Another example of a RAID 3 system is described in U.S. Pat. No. 4,092,732 to Ouchi.
A RAID 4 architecture uses the same parity error correction concept of the RAID 3 architecture, but improves on the performance of a RAID 3 system with respect to random reading of small files by "uncoupling" the operation of the individual disk drive actuators, and reading and writing a larger minimum amount of data (typically, a disk sector) to each disk(this is also known as block striping). A further aspect of the RAID 4 architecture is that a single storage unit is designated as the parity unit.
A RAID 5 architecture uses the same parity error correction concept of the RAID 4 architecture and independent actuators, but improves on the writing performance of a RAID 4 system by distributing the data and parity information across all of the available disk drives. Typically, "N+1" storage units in a set (also known as a "redundancy group") are divided into a plurality of equally sized address areas referred to as blocks. Each storage unit generally contains the same number of blocks. Blocks from each storage unit in a redundancy group having the same unit address ranges are referred to as "stripes". Each stripe has N blocks of data, plus one parity block on one storage unit containing parity for the remainder of the stripe. Further stripes each have a parity block, the parity blocks being distributed on different storage units. Parity updating activity associated with every modification of data in a redundancy group is therefore distributed over the different storage units. No single unit is burdened with all of the parity update activity. For example, in a RAID 5 system comprising 5 disk drives, the parity information for the first stripe of blocks may be written to the fifth drive; the parity information for the second stripe of blocks may be written to the further drive; the parity information for the third stripe of blocks may be written to the third drive; etc. The parity block for succeeding stripes typically "precesses" around the disk drives in a helical pattern (although other patterns may be used). Thus, no single disk drive is used for storing the parity information, as in the RAID 4 architecture. An example of a RAID 5 system is described in U.S. Pat. No. 4,761,785 to Clark et al.
The challenge posed in coupling disk array data storage systems to a multiprocessor architecture that provides for linear and orthogonal CPU and data storage expansion is in matching the I/O bandwidth of the disk array systems to the I/O capacity of the coupled CPU's. Because of the overhead cost of the array controller needed to manage a disk array, many data storage units are required within the array to achieve cost benefits by spreading the controller cost over multiple data storage units. Additionally, overall disk array system performance increases linearly with the number of data storage units within the system. Therefore, a typical disk array system includes an array controller and 3 or more disks (in some configurations, dozens of disks may be attached). However, the large number of disk in a typical disk array system often results in the array system having greater I/O performance (i.e., data transfers per second) than a single CPU can accommodate, leading to under-utilization of the data transfer capacity of the data storage units. As a consequence, the CPU's directly attached to a disk array system becomes a bottleneck for indirect accesses to the array from other CPU's. Adding additional disk array systems to other CPU's does not resolve the bottleneck problem with respect to data stored in a disk array system that is not directly coupled to such CPU's. Such an approach is also costly because the extra data transfer capacity of each disk array is not used.
It is thus difficult to match the I/O bandwidth of a disk array system to the I/O performance of multiple CPU's in a traditional multiprocessor computer system having linear and orthogonal expandability. It would be desirable to overcome such limitations while retaining the linear and orthogonal expansion characteristics of the known art.
The present invention provides a system which meets these criteria.